package com.mdnote.practice.dp;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/9/19
 * @description  最长公共子序列
 */
public class LeetCode1143 {

    public static void main(String[] args) {
        LeetCode1143 leetCode1143 = new LeetCode1143();

        String text1 = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
        String text2 = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
        int count = leetCode1143.longestCommonSubsequence(text1, text2);
        System.out.println(count);
    }
    public int longestCommonSubsequence(String text1, String text2) {
        if (text1.length() == 0 || text2.length() == 0) {
            return 0;
        }
        return dp(text1, text2);
    }

    private int dp(String text1, String text2) {

        // 创建缓存中间结果的二维数组
        int[][] dp = new int[text1.length()][text2.length()];

        // 初始化数组
        char[] text1_charArray = text1.toCharArray();
        char[] text2_charArray = text2.toCharArray();
        dp[0][0] = text1_charArray[0] == text2_charArray[0] ? 1 : 0;
        for (int i = 1; i < text1_charArray.length; i++) {
           dp[i][0] = text1_charArray[i] == text2_charArray[0] ? 1 : dp[i - 1][0];
        }
        for (int i = 1; i < text2_charArray.length; i++) {
            dp[0][i] = text2_charArray[i] == text1_charArray[0] ? 1 : dp[0][i - 1];
        }

        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                if (text1_charArray[i] != text2_charArray[j]) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                } else {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
            }
        }
        return dp[dp.length - 1][dp[0].length - 1];
    }
}
